




# 菲波那锲数列
#最简单的：  一只青蛙可以跳1或者2 级别台阶  f(n) = f(n-1)+f(n-2)  求跳N级
class Soultion:
    def __init__(self):
        self.list1 = []


    def difficulty_one(self,n):
        if n == 0:
            return 0
        if n <= 2 :
            return 1
        return self.difficulty_one(n-1) + self.difficulty_one(n-2)


    def run(self,n):
        for i in range(int(n)):
            self.list1.append(self.difficulty_one(i))
        print(self.list1)
        return self.list1


#2  一只青蛙可以跳n 级别台阶  f(n) = 2* f(n-1)  求跳N级别台阶
class Soultion2:
    def __init__(self):
        self.list1 = []


    def difficulty_two(self,n):
        if n <=1 :
            return 1
        else:
            return 2*self.difficulty_two(n-1)


    def run(self,n):
        for i in range(int(n)):
            self.list1.append(self.difficulty_two(i))
        print(self.list1)
        return self.list1

#2  一只青蛙可以跳m级别台阶  f(n) = 2* f(n-1)-f(n-m-1)  求跳n级别台阶
class Soultion3:
    def __init__(self):
        self.list1 = []


    def difficulty_three(self,m,n):
        '''

        :param m: m 是青蛙一次跳的台阶方法次数
        :param n: n 是台阶数
        :return: 返回台阶数的列表
        '''

        if n <= 1 :
            return 1

        if   m <= n  :
            return 2*self.difficulty_three(m,n-1)
        else:
            return 2*self.difficulty_three(m,n-1) - self.difficulty_three(m,n-m-1)


    def run(self,m,n):
        '''

        :param m: m 是青蛙一次跳的台阶方法次数
        :param n: n 是台阶数
        :return: 返回台阶数的列表
        '''
        for i in range(int(n)):
            self.list1.append(self.difficulty_three(m,i))
        print(self.list1)
        return self.list1

if __name__ == '__main__':
    # s = Soultion3()
    # s.run(2,5)
    s = Soultion2()
    s.run(5)
